package com.xk._03真题骗._05动态规划;

/*
 * @description: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/
 * @author: xu
 * @date: 2022/11/3 11:23
 */
public class _121买卖股票的最佳时机 {
    public int maxProfit1(int[] prices) {
        int min = prices[0], max = prices[0], maxRes = 0;
        for (int price : prices) {
            if (price > max) {
                max = price;
            } else if (price < min){
                min = max = price;
                continue;
            }
            maxRes = Math.max(maxRes, max - min);
        }
        return maxRes;
    }

    public int maxProfit2(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        // min：之前扫描的最小价格，maxRes：之前扫描过的最大利润
        int min = prices[0], maxRes = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < min){
                min = prices[i];
            } else {
                // 把第i天的股票卖出
                maxRes = Math.max(maxRes, prices[i] - min);
            }
        }
        return maxRes;
    }

    // 动态规划
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        if (prices.length == 1) return 0;
        // dp[i] 表示第i个数结尾的最大子序列和
        int dp = prices[1] - prices[0];
        int max = Math.max(0, dp);
        for (int i = 2; i < prices.length; i++) {
            int price = prices[i] - prices[i-1];
            if (dp < 0) dp = price;
            else dp += price;
            max = Math.max(max, dp);
        }
        return max;
    }
}
